这篇文章是流形学习算法总结的第一篇。我们选择了更有特色的Laplacian Eigenmap算法来进行介绍。流形学习是一种非线性的数据降维方法，主要是假设数据是分布在某个嵌入高维空间中的潜在流形这一假设来进行各类操作的。LE算法是其中的一个代表，其核心想法是利用laplace算子的特征空间来进行数据降维。本文主要参考的M.Belkin在NIPS2002的原论文: Laplacian Eigenmaps for Dimensionality Reduction and Data Representation.
流形学习的基本问题
一般的我们可以把流形学习问题转化为这样的一般性问题：给定\(N\)个样本点\(\{\boldsymbol{x}_i\}_{i=1}^N\)是\(\mathbb{R}^p\)中的点，其中\(p\)可能又一个较高的维数。根据基本假设，这些数据分布在一个嵌入在高维欧氏空间的\(d\)维流形\(\mathcal{M}\)上。这里\(d\)应当远远地小于\(p\)。数学上的流形，简单地说，就是在每个点都能找的小邻域和\(d\)维欧氏空间中的一个开集是同胚。这个同胚映射被称作一个坐标卡。事实上如果从这个观点来看，找到了坐标卡，也就找到了一个高维数据的低维表示方法。如果假设\(\boldsymbol{y}_i\)是\(\boldsymbol{x}_i\)的对应的低维表示的话，记微分同胚是\(\phi\)，那么就可以认为
\[\boldsymbol{y}_i=\phi(\boldsymbol{x}_i),\forall i\in \{1,2,\cdots,N\}\]
流行学习的主要目的就是找到\(\boldsymbol{y}_i\)和映射\(\phi\).
容易看出这不是一个良定的问题，从不同的角度出发，得到的结果是不唯一的。而我们要寻找一种降维方法，既能反应原有高维数据中的信息，又要具有较好的可解释性。而Laplacian Eigenmap是这样的方法中的一个。它希望将数据转化到Laplace算子空间中来解决数据降维的问题。为此我们首先需要回顾数据的图表示方法和图Laplace算子。
Laplacian Eigenmap算法
下面我们可以给出LE算法的主要步骤
- 建立邻接图：这里采用\(\epsilon-\)最近邻图和\(K-\)最近邻图都能够解决问题。两种方法各有利弊，前者几何解释清楚，并且邻接矩阵天然是对称的，然而参数选择有困难，并且图的连通性未必有好的保证；后者参数选择容易，且图的连接性较好，但是几何解释不清晰。
- 赋权：我们常用热核来赋给权重，即对于连通的两个点\(i,i'\),令\(w_{ii'}=\exp(-\parallel x_i-x_{i'} \parallel ^2/\sigma^2)\)；而对其它点对权值赋0. 最终我们可以用邻接矩阵\(W\)来表示这个图.
- 计算Laplace算子矩阵：完成建图后，我们定义顶点\(v_i\)的度是 \[ d_i=\sum_{i'=1}^N w_{ii'} \] 并构造一个度矩阵 \[ D=diag(d_1,\cdots,d_N) \] 由此即可得到未归一化的图Laplace矩阵 \[ L=D-W\] 容易说明, \(L\)是对称半正定矩阵，特征值是非负实数，且0是\(L\)的特征值，而特征向量是常1向量。值得说明的是我们经常采用的是经过归一化的\(L\)矩阵，规范化的方法是\[L = I - D^{-1/2}WD^{-1/2}\]
- 计算特征向量：即解以下问题：\[L\boldsymbol{f} = \lambda D\boldsymbol{f}\] 得到特征值\($0=\lambda_0 \leq \lambda_1 \leq \lambda_2 \leq \cdots \lambda_{k-1}\)
- 特征映射：（先验地）假定低维流形维数\(d\)的值，并将数据映射到特征空间上，即\[\boldsymbol{x}_i \rightarrow (\boldsymbol{f}_1(i),\cdots \boldsymbol{f}_d(i))\]
这就是LE算法进行数据降维处理的全过程。
算法原理
我们将从三个方面来解释以上算法的原理：最优映射，Laplace-Beltrami算子和热核。
最优映射
这部分我们回顾谱图理论，可以参考 Chung(1997)。当我们对数据建立了一个带权的图\(G=(V,E)\)时，考虑这样一个问题：把这个图映射到一条直线上使得图中相近的点在直线上也是相近的。我们用向量\(\boldsymbol{y}=(y_1,\cdots,y_n)^T\)表示这样的一个映射。一个衡量这个映射是不是满足保持了局部信息（图中相邻点在直线上靠近）的合理的标准是在适当的约束条件下最小化目标函数
\[\min \sum_{ij}(y_i-y_j)^2 W_{ij}\]
容易注意到如下计算
\[\begin{align}\sum_{ij}(y_i-y_j)^2W_{ij}&=\sum_{ij}(y_i^2+y_j^2-2y_iy_j)W_{ij} \\ &=\sum_i y_i^2D_{ii}+\sum_{j}y_j^2D_{jj}-2\sum_{ij}y_iy_jW_{ij} \\ &= 2 \boldsymbol{y}^TL\boldsymbol{y}\end{align}\]
因此可以把约束优化问题转化为
\[\arg \min_{\boldsymbol{y}^TD\boldsymbol{y}=1}\boldsymbol{y}^TL\boldsymbol{y}\]
这里的约束能够消除尺度的影响。而这个约束优化问题的解就是以下广义特征问题的解：
\[L\boldsymbol{y}=\lambda D\boldsymbol{y}\]
注意到常1向量是上述特征问题的解，可以增加约束获得非退化解。
现在我们再来考虑把图嵌入到\(d-\)维欧氏空间中的问题。此时嵌入映射是\(Y=[\boldsymbol{y}_1;\boldsymbol{y}_2;\cdots;\boldsymbol{y}_m]\) 通过相似的计算我们 需要最小化
\[\sum_{ij}\parallel \boldsymbol{y}^{(i)}-\boldsymbol{y}^{(j)} \parallel ^2 W_{ij}=\text{tr}(Y^TLY)\]
在约束\(Y^TDY=I\)下的解.
Laplace-Beltrami算子
Laplace算子对于一个图的作用可以类比于Laplace Beltrami算子在流形上的作用。这里我们说明为什么Laplace Beltrami算子的特征函数对于嵌入有着理想的性质。我们假设\(\mathcal{M}\)是一个光滑紧致的\(d\)维黎曼流形。如果它被嵌入到\(\mathbb{R}^p\)中（或者说是欧氏空间的光滑子流形），我们认为该流形上的黎曼度量\(g\)就是欧氏空间的诱导度量。
和对一个图相似，我们也在寻找一个能把一个流形映射到一条实轴上的映射，并且让流形上靠近的点在像集上也是靠近的。用\(f\)表示这样的映射，并且假设它是两次可微的。
考虑流形上两个靠近的点\(\boldsymbol{x},\boldsymbol{z}\in \mathcal{M}\), 对像点\(f(\boldsymbol{x}),f(\boldsymbol{z})\), 可以证明以下性质：
\[|f(\boldsymbol{x})-f(\boldsymbol{y})|\leq \text{dist}_\mathcal{M}(\boldsymbol{x},\boldsymbol{z})\parallel \nabla f(\boldsymbol{x}) \parallel +o(\text{dist}_\mathcal{M}(\boldsymbol{x},\boldsymbol{z}))\]
而如果从流形\(\mathcal{M}\)到欧氏空间是等距嵌入，那么
\[|f(\boldsymbol{x})-f(\boldsymbol{y})|\leq \parallel \boldsymbol{x}-\boldsymbol{z}\parallel \parallel \nabla f(\boldsymbol{x}) \parallel +o(\parallel \boldsymbol{x}-\boldsymbol{z}\parallel)\]
因此我们希望梯度模\(\parallel \nabla f \parallel\)能够给我们关于映射像点的距离的信息。因此保留局部信息的最佳映射可以看作是以下优化问题的解
\[\arg\min_{\parallel f \parallel_{L^2(\mathcal{M})}=1}\int_{\mathcal{M}}\parallel \nabla f \parallel ^2\]
而求解这样一个问题，就相当于求解一个相应的图上的问题
\[\min f^TLf = \frac{1}{2}\sum_{ij}(f_i-f_j)^2W_{ij}\]
根据Laplace-Beltrami算子的定义
\[\mathscr{L}(f)\overset{def}{=}-\text{div}\nabla(f)\]
由stokes公式\(\int_\mathcal{M}\langle X,\nabla f \rangle = -\int_\mathcal{M}\text{div}(X)f\)得到
\[\int_{\mathcal{M}}\parallel \nabla f \parallel ^2 = \int_{\mathcal{M}}\mathscr{L}(f)f\]
在例如rosenberg(1997)中，我们已经知道Laplace-Beltrami算子的谱是离散谱，并且具有退化解将流形映到一点上。为此，再增加一个\(f\)与退化解正交的约束，立刻得到最优映射
\[\boldsymbol{x}\rightarrow(f_1(\boldsymbol{x}),\cdots,f_m(\boldsymbol{x})))\]
热核与权重选取
为什么我们采用的热核能够当作图Laplace算子呢？我们考虑流形上扩散的热方程：
\[(\frac{\partial}{\partial t}+\mathscr{L})u=0\]
其解为
\[u(x,t)=\int_{\mathcal{M}}H_t(x,y)f(y)\]
而这里的热核在合适的局部坐标系统下，可以用高斯核来近似，即当\(x,y\)很接近时
\[H_t(x,y)\approx (4\pi t)^{-\frac{m}{2}}e^{-\frac{\parallel x-y \parallel^2}{4t}}\]
注意到在\(t\rightarrow 0\)的极限下，热核\(H_t(x,y)\rightarrow \delta(x)\)即Dirac \(\delta\)泛函，满足\(\lim_{t\rightarrow 0 }\int_\mathcal{M} H_t(x,y)f(y)=f(x)\),最终我们可以用以下表达式近似表达Laplace-Beltrami算子
\[\mathscr{L}f(x_i)=\frac{1}{t}\left[f(\boldsymbol{x}_i)-\frac{1}{k}(4\pi t)^{-\frac{d}{2}}\sum_{\boldsymbol{x}_j,0<\parallel \boldsymbol{x}_j-\boldsymbol{x}_i \parallel <\epsilon} \exp\{-\frac{\parallel \boldsymbol{x}_i-\boldsymbol{x}_j \parallel^2}{4t}\}f(\boldsymbol{x}_j) \right]\]
利用Laplace算子对常函数作用得到0的特点，可以消去未知的内在维数参数\(d\).这最终使我们采用了现在的权重选取方式.
至此已经给出对Laplacian Eigenmap原始论文算法的详尽解析。具体LE算法的应用，可以在Linguistic等领域的论文中找到。值得一提的是，这一方法由于对噪声非常敏感，有着诸多改进的版本。